package h0902;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 复原ip地址
 * @date 2024/9/2 22:47
 */
public class RestoreIP {
    public static void main(String[] args) {
        String s = "25525511135";
        System.out.println(new RestoreIP().restoreIpAddresses(s));
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        backTrack(res, s, new StringBuilder(), 0, 0);
        return res;
    }

    private void backTrack(List<String> res, String s, StringBuilder path, int start, int segment) {
        //边界条件
        if (start == s.length() && segment == 4) {
            res.add(path.toString());
            return;
        } else if (start == s.length() || segment == 4) {
            return;
        }

        for (int i = 1; i < 1 + 3; i++) {
            if (start + i > s.length()) {
                break;
            }
            String part = s.substring(start, start + i);
            if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) {
                continue;
            }
            int originalLen = path.length();

            if (segment > 0) path.append(".");
            path.append(part);

            backTrack(res, s, path, start + i, segment + 1);
            path.setLength(originalLen);
        }
    }
}
